Namespacing everything to /UVa.
[andmenj-acm.git] / UVa / 11512 - GATTACA / gattaca.4.cpp
blob9d0028ff0752f4c2d488ca9ac3ab701422f4b909
1 /*
2 Problem: G - GATTACA
3 Author: Andrés Mejía-Posada
4 (http://blogaritmo.factorcomun.org)
6 Fast. Takes 0.5 seconds on 100 hundred strings of length 1000.
8 Accepted.
9 */
11 using namespace std;
12 #include <algorithm>
13 #include <iostream>
14 #include <iterator>
15 #include <sstream>
16 #include <fstream>
17 #include <cassert>
18 #include <climits>
19 #include <cstdlib>
20 #include <cstring>
21 #include <string>
22 #include <cstdio>
23 #include <vector>
24 #include <cmath>
25 #include <queue>
26 #include <deque>
27 #include <stack>
28 #include <map>
29 #include <set>
31 int main(){
32 //freopen("gattaca.in", "r", stdin);
33 int T;
34 cin >> T;
35 while (T--){
36 string s;
37 cin >> s;
38 int n = s.size(), rep = 0;
39 string ans = "";
41 vector<string> sufijos;
42 string t = s;
43 sufijos.push_back(t);
44 while (t.size() > 0) t.erase(t.begin()), sufijos.push_back(t);
45 sort(sufijos.begin(), sufijos.end());
46 for (int k=1; k<sufijos.size(); ++k){
47 int i;
48 for (i=0; i<sufijos[k].size() && i < sufijos[k-1].size() && sufijos[k][i] == sufijos[k-1][i]; ++i);
49 if (i > 0){
50 t = sufijos[k].substr(0, i);
51 if (t == ans) ++rep;
52 else if (i > ans.size() || (i == ans.size() && t < ans)) ans = t, rep = 2;
57 //for (int i=0; i<sufijos.size(); ++i) cout << sufijos[i] << endl;
59 if (ans.empty()) cout << "No repetitions found!\n";
60 else cout << ans << " " << rep << endl;
62 return 0;